package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript:
 * @date: 2021/6/10 15:35
 * @version: 1.0
 */
public class Q70_ArrayStack { //.手写一个栈，实现 push，pop方法，以及 max获取最大的元素方法，要求时间复杂度为 O(1)
    private int maxSize;// 栈的最大容量
    private int[] stack;// 存放数据（使用数组）
    private int[] maxStack;// 存放最大数据（使用数组） fixme
    private int top = -1;// 栈顶指针 fixme,判断是空还是满都是要用这个top来的。
    public Q70_ArrayStack(int maxSize) {
        this.maxSize = maxSize;this.stack = new int[this.maxSize];// 初始化数组
    }
    public boolean isEmpty() { //判断栈空的方法：
        return this.top == -1;// 当栈顶指针为-1时代表当前栈还没有存入元素
    }// 当栈顶的指针等于栈最大容量减一时，代表栈满了（指针指向的是stack的索引，是从0开始的）。判断栈满的方法：
    public boolean isFull() { return this.top == this.maxSize - 1; }
    public void push(int value) {
        if (this.isFull()) {// 验证是否还可以压入数据，压栈（入栈）的方法：
            System.out.println("栈满了！");return;
        }
        this.top++;// 先移动栈顶指针
        this.stack[this.top] = value;// 保存数据

        if (this.isEmpty()){
            top++;
            stack[top]=value;
            maxStack[top]=value;
        }else {
            if (this.isFull()){
                System.out.println("栈满了..");
                return;
            }
            top++;
            stack[top] = value;
            if (value >= maxStack[top - 1]) {
                maxStack[top] = value;
            } else {
                maxStack[top] = maxStack[top - 1];
            }
        }
    }
    public int pop() {// 验证是否还可以取出数据，弹栈（出栈）的方法：
        if (this.isEmpty()) { throw new RuntimeException("栈空了！"); }
        int value = this.stack[this.top];// 取出栈顶数据
        this.top--;// 将栈顶指针向下移动
        return value;
    }

    public static void main(String[] args) {
        Q70_ArrayStack q70ArrayStack =new Q70_ArrayStack(11);
    }
}

